/* 
 * Binary Tree Preorder Traversal
 */

#include "../../func.h"

vector<int> preorderTraversal(TreeNode *root)
{
    vector<int> result;
    stack<TreeNode *> s;
    if (root)
        s.push(root);

    while (!s.empty())
    {
        TreeNode *p = s.top();
        s.pop();
        result.push_back(p->val);

        if (p->right)
            s.push(p->right);
        if (p->left)
            s.push(p->left);
    }
    return result;
}

//Morris
/* 
 * 如果cur无左孩子，cur向右移动（cur=cur.right）
 * 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
 * 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
 * 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）
 * 先序中序 prev好像没用
 */
vector<int> preorderTraversal(TreeNode *root)
{
    vector<int> result;
    TreeNode *cur = root, *prev = root;

    while (cur)
    {
        if (!cur->left)
        {
            result.push_back(cur->val);
            prev = cur;
            cur = cur->right;
        }
        else
        {
            TreeNode *node = cur->left;
            while (node->right && node->right != cur)
                node = node->right;
            if (!node->right)
            {
                result.push_back(cur->val);
                node->right = cur;
                prev = cur;
                cur = cur->left;
            }
            else
            {
                node->right = nullptr;
                cur = cur->right;
            }
        }
    }
    return result;
}